package com.tgy.algorithm.base._递归;

/**
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
 * 玩家A和玩家B依次拿走每张纸牌
 * 规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌
 * 玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
 */
public class _玩纸牌 {

    /**
     *            9 10 2
     * @param nums
     * @return
     */
    public static int getSuccessScore(int[] nums) {

        int len = nums.length - 1;
        return Math.max(takeFirst(nums,0,len),takeLast(nums,0,len));
    }

    public static int takeFirst(int[] nums,int left,int right) {

        if (left == right) {
            return nums[left];
        }

        int leftValue = nums[left] + takeLast(nums,left+1,right);
        int rightValue = nums[right] + takeLast(nums,left,right-1);
        return Math.max(leftValue,rightValue);
    }

    public static int takeLast(int[] nums,int left, int right) {

        // 后拿，别人都拿完了，没有可以拿的了，就返回0
        if (left == right) {
            return 0;
        }

        return Math.min(takeFirst(nums,left+1,right),
                takeFirst(nums,left,right-1));
    }

    public static void main(String[] args) {

        int successScore = getSuccessScore(new int[]{10, 100, 4});
        System.out.println(successScore);
    }
}
